\subsubsection{Übung i \buchmann{8.6.1}}
Laut Fermat-Test ist \( n \) nicht prim, wenn
\[
 a^{n - 1} \not\equiv 1 \mod n, \:\: a \not= 0
\]

Für \( n = 1111 \) und \( a = 3 \) gilt
\[
 3^{1111 - 1} \equiv 3^{1110} \equiv 166 \not\equiv 1 \mod 1111
\]

Lösung über schnelle Exponentiation (Pseudo Code in \buchmann{p. 39, Abb. 3.1}):

\begin{tabular}{|l|l|l|l|}
\hline
\textbf{result} & \textbf{exp} & \textbf{base} & \textbf{Aktuelle Potenz} \\
\hline
1 & 1110 & 3 & \( 3^{2^{0}} \mod 1111 \) \\
\hline
1 (keine Änderung, da exp gerade) & 555 & \( 3 \cdot 3 \equiv 9 \) & \( 3^{2^{1}} \mod 1111 \) \\
\hline
\( 1 \cdot 9 \equiv 9 \) & 277 & \( 9 \cdot 9 \equiv 81 \) & \( 3^{2^{2}} \mod 1111 \) \\
\hline
\( 9 \cdot 81 \equiv 729 \) & 138 & \( 81 \cdot 81 \equiv 1006 \) & \( 3^{2^{3}} \mod 1111 \) \\
\hline
729 & 69 & \( 1006 \cdot 1006 \equiv 1026 \) & \( 3^{2^{4}} \mod 1111 \) \\
\hline
\( 729 \cdot 1026 \equiv 251 \) & 34 & \( 1026 \cdot 1026 \equiv 559 \) & \( 3^{2^{5}} \mod 1111 \) \\
\hline
251 & 17 & \( 559 \cdot 559 \equiv 290 \) & \( 3^{2^{6}} \mod 1111 \) \\
\hline
\( 251 \cdot 290 \equiv 575 \) & 8 & \( 290 \cdot 290 \equiv 775 \) & \( 3^{2^{7}} \mod 1111 \) \\
\hline
575 & 4 & \( 775 \cdot 775 \equiv 685 \) & \( 3^{2^{8}} \mod 1111 \) \\
\hline
575 & 2 & \( 685 \cdot 685 \equiv 383 \) & \( 3^{2^{9}} \mod 1111 \) \\
\hline
575 & 1 & \( 383 \cdot 383 \equiv 37 \) & \( 3^{2^{10}} \mod 1111 \) \\
\hline
\( 575 \cdot 37 \equiv 166 \) & 0 & - & - \\
\hline
\end{tabular}

(Binärdarstellung von 1110: \( 10001010110 = 2^{10} + 2^6 + 2^4 + 2^2 + 2^1 \))